class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        # 长度不相等，这么旋转都等不到 目标值
        if len(s) != len(goal):
            return False
        # s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 == 拼接字符串在两个 s 中寻找
        s = s + s
        def build_next(s):
            next = [0]
            i = 1
            length = 0
            while i < len(s):
                if s[length] == s[i]:
                    length += 1
                    next.append(length)
                    i += 1
                else:
                    # 查表 找不到，添加0 遍历到下一个字符
                    if length == 0:
                        next.append(0)
                        i += 1
                    else:
                        length = next[length - 1]
            return next

        def KMP(s, c):
            next = build_next(c)
            i = 0
            j = 0
            while i < len(s):
                if s[i] == c[j]:
                    i += 1
                    j += 1
                elif j > 0:
                    j = next[j - 1]
                else:  # 为第一个元素
                    i += 1
                if j == len(c):
                    return True
            return False

        return KMP(s, goal)


